/// 预计算的素数序列用于哈希表扩容
const HASH_TABLE_PRIMES: &[u32] = &[
    193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317,
    196613, 393241, 786433, 1572869, 3145739, 6291469,
    12582917, 25165843, 50331653, 100663319, 201326611,
    402653189, 805306457, 1610612741,
];

/// 素数数组的长度
const HASH_TABLE_NUM_PRIMES: usize = HASH_TABLE_PRIMES.len();


/// 哈希表键值对存储结构
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct HashTablePair<K, V> {
    /// 哈希表键
    pub key: K,
    /// 哈希表值
    pub value: V,
}


/// 哈希表条目结构，使用链表法解决哈希冲突
#[derive(Debug)]
pub struct HashTableEntry<K, V> {
    /// 当前节点存储的键值对
    pub pair: HashTablePair<K, V>,
    /// 下一个哈希表条目的可选智能指针
    pub next: Option<Box<HashTableEntry<K, V>>>,
}
/// 哈希表主结构，采用链表法解决冲突，支持自动扩容。
///
/// 该结构包含存储键值对的桶数组、哈希函数、比较函数以及扩容所需的元数据。
///
/// # 类型参数
/// - `K`: 键类型
/// - `V`: 值类型
/// - `H`: 哈希函数类型，需实现 `Fn(&K) -> u64`
/// - `E`: 键比较函数类型，需实现 `Fn(&K, &K) -> bool`
#[derive(Debug)]
pub struct HashTable<K, V, H, E> {
    /// 哈希桶数组，每个桶存储链表头节点
    table: Vec<Option<Box<HashTableEntry<K, V>>>>,
    /// 当前哈希表容量（桶的数量）
    table_size: u32,
    /// 用于计算键哈希值的函数
    hash_func: H,
    /// 用于比较键是否相等的函数
    equal_func: E,
    /// 当前存储的键值对总数
    entries: u32,
    /// 当前使用的素数在预计算数组中的索引
    prime_index: usize,
    key_free_func: Option<fn(K)>,
    value_free_func: Option<fn(V)>,
}
impl<K, V, H, E> HashTable<K, V, H, E> 
where
    H: Fn(&K) -> u64,
    E: Fn(&K, &K) -> bool,
{
    /// 创建新的哈希表实例
    ///
    /// # 参数
    /// - `hash_func`: 哈希计算函数
    /// - `equal_func`: 键相等判断函数
    /// - `initial_size`: 初始容量，会自动调整到最近的素数
    ///
    /// # 返回值
    /// 返回初始化后的哈希表实例
    pub fn new(hash_func: H, equal_func: E, initial_size: u32) -> Self {
        let mut instance = Self {
            table: Vec::new(),
            table_size: 0,
            hash_func,
            equal_func,
            entries: 0,
            prime_index: 0,
            key_free_func: None,
            value_free_func: None,
        };
        instance.allocate_table();
        instance
    }

    /// 分配新的哈希表存储空间
    ///
    /// 根据预计算的素数数组确定新表大小，当超过素数数组范围时按条目数10倍扩容。
    /// 初始化所有哈希桶为None表示空链表。
    ///
    /// # 返回值
    /// 总是返回true，因为Rust的Vec分配在正常情况不会失败
    fn allocate_table(&mut self) -> bool {
        let new_table_size = if self.prime_index < HASH_TABLE_NUM_PRIMES {
            HASH_TABLE_PRIMES[self.prime_index]
        } else {
            self.entries * 10
        } as u32;

        self.table_size = new_table_size;
        self.table = (0..new_table_size as usize).map(|_| None).collect();
        true
    }
}

impl<K, V, H, E> HashTable<K, V, H, E> {
    /// 获取当前哈希表中存储的键值对数量
    ///
    /// # 返回值
    /// 返回当前存储的键值对总数
    pub fn num_entries(&self) -> u32 {
        self.entries
    }

    /// 注册自定义内存释放函数用于键值资源管理
    pub fn register_free_functions(
        &mut self,
        key_free_func: Option<fn(K)>,
        value_free_func: Option<fn(V)>,
    ) {
        self.key_free_func = key_free_func;
        self.value_free_func = value_free_func;
    }
}

/// 哈希表迭代器，用于安全遍历哈希表所有条目
#[derive(Debug)]
pub struct HashTableIterator<'a, K, V, H, E> {
    /// 关联的哈希表引用
    hash_table: &'a HashTable<K, V, H, E>,
    /// 当前遍历的链表节点
    current_entry: Option<&'a HashTableEntry<K, V>>,
    /// 当前遍历的桶索引
    current_bucket: usize,
}

impl<K, V, H, E> HashTable<K, V, H, E> 
where
    H: Fn(&K) -> u64,
    E: Fn(&K, &K) -> bool,
{
    /// 查找键对应的值
    /// 查找键对应的值
    pub fn lookup(&self, key: &K) -> Option<&V> {
        let hash = (self.hash_func)(key);
        let index = (hash % self.table_size as u64) as usize;

        let mut current = self.table[index].as_deref();
        while let Some(entry) = current {
            if (self.equal_func)(key, &entry.pair.key) {
                return Some(&entry.pair.value);
            }
            current = entry.next.as_deref();
        }

        None
    }
}
impl<K, V, H, E> HashTable<K, V, H, E> 
where
    H: Fn(&K) -> u64,
    E: Fn(&K, &K) -> bool,
{
    /// 扩展哈希表容量并重新哈希所有条目
    /// 
    /// # 返回值
    /// 成功返回true，失败返回false
    fn enlarge(&mut self) -> bool {
        let old_table = std::mem::replace(&mut self.table, Vec::new());
        let old_table_size = self.table_size;
        let old_prime_index = self.prime_index;

        self.prime_index += 1;
        if !self.allocate_table() {
            self.table = old_table;
            self.table_size = old_table_size;
            self.prime_index = old_prime_index;
            return false;
        }

        for mut bucket in old_table {
            let mut current = bucket.take();
            while let Some(mut entry) = current.take() {
                let next = entry.next.take();
                let hash = (self.hash_func)(&entry.pair.key);
                let index = (hash % self.table_size as u64) as usize;
                
                entry.next = self.table[index].take();
                self.table[index] = Some(entry);
                current = next;
            }
        }
        true
    }
    pub fn insert(&mut self, key: K, value: V) -> bool {
        if self.entries * 3 > self.table_size {
            if !self.enlarge() {
                return false;
            }
        }

        let hash = (self.hash_func)(&key);
        let index = (hash % self.table_size as u64) as usize;

        let mut current = &mut self.table[index];
        while let Some(entry) = current {
            if (self.equal_func)(&entry.pair.key, &key) {
                let old_key = std::mem::replace(&mut entry.pair.key, key);
                let old_value = std::mem::replace(&mut entry.pair.value, value);
                if let Some(free_key) = self.key_free_func {
                    free_key(old_key);
                }
                if let Some(free_value) = self.value_free_func {
                    free_value(old_value);
                }
                return true;
            }
            current = &mut entry.next;
        }

        let new_entry = Box::new(HashTableEntry {
            pair: HashTablePair { key, value },
            next: self.table[index].take(),
        });
        self.table[index] = Some(new_entry);
        self.entries += 1;
        true
    }
}


impl<K, V, H, E> HashTable<K, V, H, E> 
where
    H: Fn(&K) -> u64,
    E: Fn(&K, &K) -> bool,
{
    /// 从哈希表中移除指定键对应的条目。
    ///
    /// 该方法会计算键的哈希值以确定对应的桶，然后遍历该桶的链表查找匹配的键。
    /// 如果找到匹配的条目，将解除链表中的链接并释放相关资源，同时减少条目计数。
    ///
    /// # 参数
    /// - `key`: 要移除的键的引用
    ///
    /// # 返回值
    /// - 如果成功找到并移除了条目，返回 `true`
    /// - 如果未找到对应的键，返回 `false`
    pub fn remove(&mut self, key: &K) -> bool {
        let hash = (self.hash_func)(key);
        let index = (hash % self.table_size as u64) as usize;

        let mut head = &mut self.table[index];
        loop {
            match head.take() {
                None => break,
                Some(mut entry) => {
                    if (self.equal_func)(key, &entry.pair.key) {
                        *head = entry.next.take();
                        self.entries -= 1;
                        
                        if let Some(free_key) = self.key_free_func {
                            free_key(entry.pair.key);
                        }
                        if let Some(free_value) = self.value_free_func {
                            free_value(entry.pair.value);
                        }
                        return true;
                    } else {
                        let next = entry.next.take();
                        entry.next = next;
                        *head = Some(entry);
                        head = &mut head.as_mut().unwrap().next;
                    }
                }
            }
        }
        false
    }
}

impl<'a, K, V, H, E> HashTableIterator<'a, K, V, H, E> {
    pub fn next(&mut self) -> Option<&'a HashTablePair<K, V>> {
        while let Some(entry) = self.current_entry {
            let pair = &entry.pair;
            self.current_entry = entry.next.as_deref();
            return Some(pair);
        }

        while self.current_bucket < self.hash_table.table.len() - 1 {
            self.current_bucket += 1;
            if let Some(entry) = self.hash_table.table[self.current_bucket].as_deref() {
                self.current_entry = Some(entry);
                return self.next();
            }
        }

        None
    }
}

impl<'a, K, V, H, E> HashTable<K, V, H, E> {
    /// 创建并初始化哈希表迭代器
    ///
    /// 自动定位第一个非空桶作为迭代起点
    pub fn iter(&'a self) -> HashTableIterator<'a, K, V, H, E> {
        let mut iterator = HashTableIterator {
            hash_table: self,
            current_entry: None,
            current_bucket: 0,
        };

        // 遍历桶数组寻找第一个有效条目
        for (index, bucket) in self.table.iter().enumerate() {
            if let Some(entry) = bucket.as_deref() {
                iterator.current_entry = Some(entry);
                iterator.current_bucket = index;
                break;
            }
        }

        iterator
    }
}